//集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

//给定一个数组 nums 代表了集合 S 发生错误后的结果。

//请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
// 步骤： 一、首先需要一个[1, 2, ...n]的数组作为辅助，假设重复元素为dup，丢失元素为mis。将原数组和辅助数组所有元素进行异或，可知其中等于dup的有3个，mis有1个（在辅助数组中），其余元素各有2个。在异或运算过程中，成对出现的都会抵消为0（异或运算的先后顺序不影响，故可当做相等元素各自运算）。最后的结果就是 dup ^ mis. 例：
// 1 001 1 001 2 010 2 010 2 010 3 011 4 100 4 100 将上面8个元素进行异或，相等元素抵消后，结果就是 2 ^ 3 ，结果是001, 将其保存为sum。

// 二、第二步的目的是将dup和mis分开来处理。通过第一步的处理可知，对于sum而言，其中“1”所在的位置就是dup和mis不相同的位（必定是一个为‘0’，一个为‘1’），按照这个思路将dup和mis分开：这样的1有若干个，不妨将最靠右的1作为鉴别点，重新将上述8个元素分为两部分，则dup和mis在不同的两部分。 1 001 1 001 2 010 2 010 2 010 3 011 4 100 4 100 对于这个例子，我们按照第0位是否为1将它们分类，假设对应位是‘0’为a0类，对应位是‘1’为a1类（粗体）。

// 注：这里实现分类的方法是: 令t = sum & (-sum),然后将t与所有元素分别按位与，结果不为零则该元素此位为‘1’，否则为‘0’。 其具体原理是：-sum是负数，用补码（反码+1）表示，对于上述的与运算，sum和自己的反码按位与一定为0，但是补码是反码+1，从最低位看起，若原码为‘0’，则其补码为‘0’且向上进位，此位与结果为0； 左移一位继续分析，只要一直是0，补码也一直是0，且向上进位； 直至遇到原码为‘1’的位，此时补码也是1（0+进位的1），此位与的结果是1，其不再进位； 此时高位的与结果均为0.

// 例子中sum二进制为 001， -sum为111，按位与结果为‘001’，将‘001’分别与各元素按位与，若结果为1则该元素此位为‘1’，分为a1，否则为‘0’， 分为a0。

// 三、将dup和mis分开为两部分后，发现一部分有3个dup，其余元素成对出现；另一部分有1个mis，其余元素成对出现。 对于这两部分，各自将自身所有元素按位异或^，发现结果正好一个是dup，一个是mis。剩下的工作就非常简单了，只需要区分出dup和mis即可，将两个结果分别设为xor1和xor2，任取一个，计算其在nums数组中出现的次数，若为0，则此数为mis，另一个为dup；若为2，则此数为dup，另一个为mis。

// 例子中a0部分异或结果为010（2），a1部分结果为011（3），取2在nums数组中比较，count == 2出现两次，故dup=2，mis=3.

// 作者：锋锋
// 链接：https://leetcode.cn/problems/set-mismatch/solutions/248566/cyi-huo-fa-xiang-jie-by-feng-feng-19/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
int* findErrorNums(int* nums, int numsSize, int* returnSize){
    int*ans=(int*)malloc(sizeof(int)*2);
    int ret=0;
    *returnSize=2;
    int pos=0;
    int xor1=0;
    int xor2=0;
    int dup=0;
    int mis=0;
    for(int i=1;i<=numsSize;i++)
    {
        ret^=i;
    }
    for (int i = 0; i < numsSize; i++)
    {
        ret ^= nums[i];
    }
    for(int i=0;i<32;i++)
    {
        if((ret>>i)&1==1)
        {
            pos=i;
            break;
        }
    }
    //将dup与mis分开
    for (int i = 0; i < numsSize; i++)
	{
		if(((nums[i]>>pos)&1)==1)
        {
            xor1^=nums[i];
        }
        else
        {
            xor2^=nums[i];
        }
	}
    for(int i=1;i<=numsSize;i++)
    {
        if(((i>>pos)&1)==1)
        {
            xor1^=i;
        }
        else
        {
            xor2^=i;
        }
    }
    int count=0;
    for(int i=0;i<numsSize;i++)
    {
        if(nums[i]==xor1)
        {
            count++;
        }
    }
    if(count==0)
    {
        mis=xor1;
        dup=xor2;
    }
    else
    {
        mis=xor2;
        dup=xor1;
    }
    ans[0]=dup;
    ans[1]=mis;
    return ans;
}